package chapter01;

public class Trap {
    /**
     *  双指针
     *  ...i... 只看i位置的水柱可以储存多少水
     *  |left......right| 只看left/right位置可以存储多少水
     *  left左边有[0...left-1]水柱最大值leftMax  right右边有[right+1...length-1]水柱最大值rightMax
     *  1)leftMax<rightMax
     *     [left]水柱只能在|leftMax...rightMax|这两个外围平板间存储 但短板决定水量最多可以存储多少
     *     sum=sum+max{leftMax-[left],0}
     *     更新leftMax=max{leftMax,[left]}
     *     左指针移动 left++
     *  2)leftMax<=rightMax
     *      sum=sum+{rightMax-[right],0}
     *      更新rightMax=max{rightMax,[right]}
     *      右指针移动
     *  细节：
     *      初始化双指针left、right指向1，length-2
     *      [0]左边无水柱 水会从左边流走 能存储0
     *      [length-1]右边无水柱 水会从右边流走 能存储0
     */
    public int trap(int[] height) {
        int leftMax=height[0];
        int rightMax=height[height.length-1];
        int left=1;
        int right=height.length-2;
        int sum=0;
        while(left<=right){
            if(leftMax<rightMax){
                sum=sum+Math.max(leftMax-height[left],0);
                leftMax=Math.max(leftMax,height[left++]);
            }else{
                sum=sum+Math.max(rightMax-height[right],0);
                rightMax=Math.max(rightMax,height[right--]);
            }
        }
        return sum;
    }
}
